package com.berchen.offer;

/**
 * 给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。下图为一棵有9个节点的二叉树。树中从父节点指向子节点的指针用实线表示，从子节点指向父节点的用虚线表示
 *
 * 给定一个节点  根据该节点找到根节点  然后中序遍历 找到中序遍历中的该节点的下一个节点
 */
public class Test09 {
    public static void main(String[] args) {
        TreeLinkNode root=new TreeLinkNode(8);
        TreeLinkNode node6=new TreeLinkNode(6);
        TreeLinkNode node10=new TreeLinkNode(10);
        TreeLinkNode node5=new TreeLinkNode(5);
        TreeLinkNode node7=new TreeLinkNode(7);
        TreeLinkNode node9=new TreeLinkNode(9);
        TreeLinkNode node11=new TreeLinkNode(11);
        root.left=node6;
        root.right=node10;
        node6.next=root;
        node6.left=node5;
        node6.right=node7;
        node5.next=node6;
        node7.next=node6;
        node10.next=root;
        node10.left=node9;
        node10.right=node11;
        node9.next=node10;
        node11.next=node10;
        Test09 test09 = new Test09();
        TreeLinkNode treeLinkNode = test09.GetNext(root);
        System.out.println(treeLinkNode);
    }

    private boolean flag=false;
    public TreeLinkNode GetNext(TreeLinkNode pNode) {

        if(pNode==null){
            return null;
        }
        TreeLinkNode temp=pNode;
        while (temp.next!=null){
            temp=temp.next;
        }
        return diGUI(temp, pNode.val);
    }
    public TreeLinkNode diGUI(TreeLinkNode node,int value){


        if(node==null){
            return null;
        }
        TreeLinkNode result=diGUI(node.left,value);
        // 这里必须加result==null 否则会出现错误 递归回来会把上一层的数据给返回回去
        if(flag&&result==null){
            return node;
        }
        if(node.val==value){
            flag=true;
        }
        if(result==null) {
            result=diGUI(node.right, value);
        }
        return result;
    }
}
